<script src="../utils/getRandom.js"></script>
<script>
	function quicksort(arr) {
		let len = arr.length;
		if(len <= 1) return arr;

		let midpoint = getRandom(0, len-1),
			middle = arr[midpoint];

		let left_arr = [];
		for(let i = 0; i < arr.length; i++) {
			if(i===midpoint) continue;
			if(arr[i] <= middle) { left_arr.push(arr[i]) }
		}
		let leftarr = quicksort(left_arr);

		let right_arr = [];
		for(let i = 0; i < arr.length; i++) {
			if(i===midpoint) continue;
			if(arr[i] > middle) { right_arr.push(arr[i]) }
		}
		let rightarr = quicksort(right_arr);

		return [...leftarr, middle, ...rightarr];
	}


	let arr = [1, 4, 2, 3, 6, 5, 100, 99, 88, 89];
	let res = quicksort(arr);
	console.log(res);
</script>